/*
 * skipset.h
 * new type must be a number and only a number!!
 *
 *  Created on: Mar 25, 2012
 *      Author: Stephen
 */

#ifndef SKIPSET_H_
#define SKIPSET_H_

template<typename V> class SkipSet
{
private:
	typedef struct snode {
		V var,key;
		struct snode *next,*down;
	}node;

	node *top;
	int percentage;
public:
	SkipSet();
	SkipSet(int percentage);
	~SkipSet();
	int ins(V key, V data);
	int del(V key);
	int get(V key, V *data);
	void print();
	void print(int p);
};

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include "rand100.h"

using std::cout;
using std::endl;
using std::setw;

template<typename V>
SkipSet<V>::SkipSet()
{
	percentage = 33;
	top = new node;
	top->key = top->var = 0;
	top->down = top->next = 0;
}

template<typename V>
SkipSet<V>::SkipSet(int percentage)
{
	if(percentage < 0 || percentage > 99)
	{
		cout << "Invalid percentage, defaulting to 33.\n" << endl;
		this->percentage = 33;
	}
	else
		this->percentage = percentage;
	top = new node;
	top->key = top->var = 0;
	top->down = top->next = 0;
}

template<typename V>
SkipSet<V>::~SkipSet()
{
	node *current,*temp;

	while(1)
	{
		current = top;
		if(top != 0 && top->down != 0)
			top = top->down;
		else if(top != 0)
			top = 0;
		while(current != 0)
		{
			temp = current;
			current = current->next;
			delete temp;
		}
		if(current != 0)
		{
			delete current;
		}
		else
			break;
	}
}

template<typename V>
int SkipSet<V>::ins(V key, V data)
{
	node *current;
	current = top;

	while(1)
	{
		while(current->next != 0 && current->next->key <= key)
		{	/*Check current list while current->next exists*/
			if(key == current->next->key) /*Already exists*/
				return 0;
			current = current->next;
		}
		if(current->down == 0) /*Break if already on bottom level*/
			break;
		current = current->down;
	}

	node *newL;
	newL = new node;
	newL->key = key;
	newL->var = data;
	newL->down = 0;
	newL->next = current->next;
	current->next = newL;


	int level = 0;
	while(rand100()<=percentage) /*Conditional to add to higher level*/
	{
		if(level == top->key) /*New level*/
		{
			newL = new node; /*New head*/
			if(newL == 0) return -1;
			newL->key = ++level;
			newL->var = 0; /*Will be incremented later*/
			newL->down = top;
			newL->next = 0;
			top = newL;

			newL = new node; /*New element for the level*/
			if(newL == 0) return -1;
			newL->key = key;
			newL->var = data;
			newL->down = current->next;
			newL->next = 0;

			top->next = newL;

			current = top;
		}
		else if(level < top->key) /*Existing level*/
		{
			node *temp; /*Hold lower level of the same element*/
			temp = current->next;

			current = top;
			level++;
			while(current->key > level) /*Move to next level*/
			{
				current = current->down;
			}

					/*Move to insertion spot*/
			while(current->next != 0 && current->next->key < key)
			{
				current = current->next;
			}

			newL = new node; /*New element for level*/
			if(newL == 0) return -1;
			newL->key = key;
			newL->var = data;
			newL->down = temp; /*Reference to lower level same element*/
			newL->next = current->next;

			current->next = newL;
		}
	}

	/*Increment level counters*/
	current = top;
	while(current->key > level)
	{
		current = current->down;
	}
	current->var++;
	while(current->down != 0)
	{
		current = current->down;
		current->var++;
	}
	return 1;
}

template<typename V>
int SkipSet<V>::del(V key)
{
	node *current;
	current = top;
	int level = (int)current->key;
	int found = 0;

	while(1)
		{
			while(current->next != 0 && current->next->key <= key)
			{
				if(key == current->next->key)
				{
					found = 1;
					break;
				}
				current = current->next;
			}
			if(current->down == 0 || found == 1)
				break;
			current = current->down;
			level--;
		}

	if(found)
	{
		node *temp;
		while(level > 0) /*while current level is not zero level*/
		{
			/*Remove on current level*/
			temp = current->next;
			current->next = current->next->next;
			delete temp;

			/*Decrement level element counter*/
			temp = top;
			while(temp->key > level)
			{
				temp = temp->down;
			}
			temp->var--;

			/*Remove empty level check*/
			if(top->var == 0)
			{
				current = top;
				top = top->down;
				delete current;
				current = top;
			}
			else
				current = current->down;
			/*Move current to correct spot*/
			while(current->next->key != key)
			{
				current = current->next;
			}
			level--;
		}

		/*Remove from 0 level*/
		temp = current->next;
		current->next = current->next->next;
		delete temp;

		/*Decrement counter from 0 level*/
		temp = top;
		while(temp->key != 0)
		{
			temp = temp->down;
		}
		temp->var--;

		return 1;
	}

	return 0;
}

template<typename V>
int SkipSet<V>::get(V key, V *data)
{
	node *current;
	current = top;
	/*searches for value*/
	while(1)
		{
			while(current->next != 0 && current->next->key <= key)
			{
				if(key == current->next->key)
				{
					*data = current->next->var;
					return 1;
				}
				current = current->next;
			}
			if(current->down == 0)
				return 0;
			current = current->down;
		}
}

template<typename V>
void SkipSet<V>::print()
{
	print(0);
}

template<typename V>
void SkipSet<V>::print(int p)
{
	node *current;
	current = top;

	std::ostringstream bah;

	while(current->key > -1)
	{
		bah << setw(6) << current->key << " | " << setw(9) << current->var << "\n";
		if(current->down != 0)
			current = current->down;
		else
			break;
	}

	cout << "Current size   :" << current->var << "\n";
	cout << "Levels         :" << top->key + 1 << "\n";
	cout << "Level  | Elements\n";
	cout << bah.str() << endl;

	if(p != 0)
	{
		cout << "The records: " << endl;

		current = top;
		while(current->key > 0) /*Go to bottom level for printing*/
			current = current->down;
		while(current->next != 0) /*Go across level for printing*/
		{
			cout << "{" << current->next->key << ", " << current->next->var << "}";
			current = current->next;
			if(current->next != 0)
				cout << " ";
		}
		cout << "\n" << endl;
	}
	cout << "------------------------------\n";
}

#endif /* SKIPSET_H_ */
